<?php
namespace common\lib;
use Yii;
use yii\base\Exception;

class LRtree
{
    private $model;
    private $parent = 'parent';
    private $left = 'lft';
    private $right = 'rgt';
    private $grate = 'grade';
    private $where;
    public function __construct($model, $conditions = null)
    {
        $this->model = $model;
        $this->where = $this->setWhere($conditions);
    }
    public function node()
    {
        if ($this->model->isNewRecord) {
            $this->addNode();
        } else {
            $this->moveNode();
        }
    }
    /**
     * 添加节点
     * $this->parent
     *      NULL    此节点为顶级节点
     */
    public function addNode()
    {
        if ($this->parent == null || !str_replace(' ', '', $this->model->{$this->parent})) {
            $this->addTopNode();
        } else {
            $this->addChildNode();
        }
    }
    public function addTopNode()
    {
        /**
         * 获取分类树最大右值
         */
        $maxR = $this->model->getDb()->createCommand(
            "select
                     max($this->right)
                 from
                     {$this->model->tableName()}
                 where
                     {$this->buildWhere()}"
        )->queryColumn()[0];
        if ($maxR == null) {
            $maxR = -1;
        }
        $this->model->{$this->left} = $maxR + 1;
        $this->model->{$this->right} = $maxR + 2;
        $this->model->{$this->grate} = 1;
    }
    public function addChildNode()
    {
        $parent = $this->model->findOne($this->model->{$this->parent});
        if ($parent == null) {
            throw new Exception('没有此分类');
        }
        $this->model->{$this->grate} = $parent->{$this->grate} + 1;
        $maxR = $parent->{$this->right};
        $status1 = $this->model->updateAllCounters(
            array(
                $this->right => 2,
            ),
            $this->buildWhere(
                [
                    ['>', $this->right, $parent->{$this->right}]
                ]
            )
        );
        $status2 = $this->model->updateAllCounters(
            array(
                $this->left => 2,
            ),
            $this->buildWhere(
                [
                    ['>', $this->left, $parent->{$this->right}]
                ]
            )
        );
        $max = $this->model->updateAllCounters(
            array(
                $this->right => 2
            ),
            [
                $this->model->primaryKey()[0] => $parent->getPrimaryKey()
            ]
        );
        if ($status1 || $status2 || $max) {
            $this->model->{$this->left} = $maxR;
            $this->model->{$this->right} = $maxR + 1;
            $this->model->{$this->grate} = $parent->{$this->grate} + 1;
        } else {
            throw new Exception('分类匹配错误2');
        }
    }
    public function moveNode()
    {
        $isTop = false;
        //查询是否存在新的父类节点
        if ($this->parent == null) {
            return true;
        }
        $parent = $this->model->findOne($this->model->{$this->parent});
        //不存在父类节点,就是移动到顶层节点
        if ($parent == null) {
            if ($this->model->{$this->grate} == 1) {
                return true;
            }
            $isTop = true;
        } else {
            //判断新移动的节点是否可以移动
            if ($parent->getPrimaryKey() == $this->model->getPrimaryKey()) {
                throw new Exception('不能移动自身');
            }
            if ($this->model->{$this->left} < $parent->{$this->left} && $this->model->{$this->right} > $parent->{$this->right}) {
                throw new Exception('夫节点不能移动到其子节点');
            }
            if ($parent->getPrimaryKey() == $this->parent) {
                return true;
            }
        }
        //要删除节点的偏移量
        $differ = -($this->model->{$this->right} - $this->model->{$this->left} + 1);
        //把要移动的节点dr都加上10
        $move = $this->model->updateAllCounters(
            [
                'dr' => 10
            ],
            $this->buildWhere(
                [
                    ['>=', $this->left, $this->model->{$this->left}],
                    ['<=', $this->left, $this->model->{$this->right}],
                ]
            )
        );
        //把DR值<2的都更新左右值,即是 0 和 1
        $this->counters($differ,
            [
                ['>', $this->left, $this->model->{$this->right}],
                ['<', 'dr', 2]
            ],
            [
                ['>', $this->right, $this->model->{$this->right}],
                ['<', 'dr', 2]
            ]
        );
        //移动节点的偏移量
        $move_differ = 0;
        //移动节点的层级的偏移量
        $grate_differ = 0;
        if ($isTop) {
            //查询最大右值
            $maxR = $this->model->getDb()->createCommand(
                "select
                     max($this->right)
                 from
                     {$this->model->tableName()}
                 where
                     {$this->buildWhere()}"
            )->queryColumn()[0];
            $move_differ = $maxR - $this->model->{$this->left} + 1;
            $grate_differ = 1 - $this->model->{$this->grate};
        } else {
            //查询新父类的左右值
            $parent = $this->model->findOne($this->model->{$this->parent});
            //根据偏移量,移动节点,预留位置给移动节点
            $this->counters(abs($differ),
                [
                    ['>', $this->left, $parent->{$this->right}],
                    ['<', 'dr', 2]
                ],
                [
                    ['>=', $this->right, $parent->{$this->right}],
                    ['<', 'dr', 2]
                ]
            );
            //查询更新后父类节点的值
            $parent = $this->model->findOne($this->model->{$this->parent});
            $move_differ = $parent->{$this->right} - $this->model->{$this->right} - 1;
            $grate_differ = $parent->{$this->grate} - $this->model->{$this->grate} + 1;
        }
        $this->model->updateAllCounters(
            [
                $this->left => $move_differ,
                $this->right => $move_differ,
                $this->grate => $grate_differ,
                'dr' => -10
            ],
            $this->buildWhere(
                [
                    ['>', 'dr', 2],
                ]
            )
        );
    }
    public function checkHaveChild()
    {
        $num = $this->model->getDb()->createCommand(
            "select
                     count($this->right)
                 from
                     {$this->model->tableName()}
                 where
                     {$this->buildWhere([
                        ['>', $this->left, $this->model->{$this->left}],
                        ['<', $this->left, $this->model->{$this->right}]
                 ])}"
        )->queryColumn()[0];
        if ($num > 0) {
            throw new Exception('此节点不是末级节点, 不能删除');
        }
    }
    public function delNode()
    {
        $this->checkHaveChild();
        $differ = -($this->model->{$this->right} - $this->model->{$this->left} + 1);
        $this->counters($differ,
            [['>', $this->left, $this->model->{$this->right}]],
            [['>', $this->right, $this->model->{$this->right}]]
        );
//        {
        return true;
//        }
//        throw new Exception('删除节点失败');
    }
    public function counters($differ, $left, $right)
    {
        $l = $this->model->updateAllCounters(
            [
                $this->left => $differ,
            ],
            $this->buildWhere($left)
        );
        $r = $this->model->updateAllCounters(
            [
                $this->right => $differ,
            ],
            $this->buildWhere($right)
        );
        if ($l || $r) {
            return true;
        }
        return false;
    }
    public function moveUp()
    {
        $neighborWhere = array();
        if ($this->model->{$this->grate} != 1) {
            $parent = $this->findParent([
                ['=', $this->grate, $this->model->{$this->grate} - 1],
                ['<', $this->left, $this->model->{$this->left}],
                ['>', $this->right, $this->model->{$this->right}],
            ]);
            if (!$parent) {
                throw new Exception('找不到其父类');
            }
            $neighborWhere = [
                ['=', $this->grate, $this->model->{$this->grate}],
                ['>', $this->left, $parent[$this->left]],
                ['<', $this->left, $this->model->{$this->left}],
            ];
        } else {
            $neighborWhere = [
                ['=', $this->grate, $this->model->{$this->grate}],
                ['<', $this->left, $this->model->{$this->left}]
            ];
        }
        $neighbor = $this->findNeighbor($neighborWhere);
        if (!$neighbor) {
            throw new Exception('已最上级');
        }
        if ($neighbor[$this->grate] != $this->model->{$this->grate}) {
            throw new Exception('不同级别,不能移动');
        }
        $upIds = $this->findNodeIds([
            ['>=', $this->left, $this->model->{$this->left}],
            ['<=', $this->left, $this->model->{$this->right}]
        ]);
        $downIds = $this->findNodeIds([
            ['>=', $this->left, $neighbor[$this->left]],
            ['<=', $this->left, $neighbor[$this->right]],
        ]);
        if (sizeof($upIds) && sizeof($downIds)) {
            $up = $this->idToString($upIds);
            $down = $this->idToString($downIds);
            $up_differ = -abs($neighbor[$this->left] - $this->model->{$this->left});
            $down_differ = abs($this->model->{$this->right} - $neighbor[$this->right]);
            $this->counters($up_differ, [$up], [$up]);
            $this->counters($down_differ, [$down], [$down]);
        } else {
            throw new Exception('数据错误');
        }
    }
    public function moveDown()
    {
        $neighborWhere = array();
        if ($this->model->{$this->grate} != 1) {
            $parent = $this->findParent([
                ['=', $this->grate, $this->model->{$this->grate} - 1],
                ['<', $this->left, $this->model->{$this->left}],
                ['>', $this->right, $this->model->{$this->right}],
            ]);
            if (!$parent) {
                throw new Exception('找不到其父类');
            }
            $neighborWhere = [
                ['=', $this->grate, $this->model->{$this->grate}],
                ['<', $this->right, $parent[$this->right]],
                ['>', $this->right, $this->model->{$this->right}],
            ];
        } else {
            $neighborWhere = [
                ['=', $this->grate, $this->model->{$this->grate}],
                ['>', $this->left, $this->model->{$this->left}]
            ];
        }
        $neighbor = $this->findNeighbor($neighborWhere, '');
        if (!$neighbor) {
            throw new Exception('已最下级');
        }
        if ($neighbor[$this->grate] != $this->model->{$this->grate}) {
            throw new Exception('不同级别,不能移动');
        }
        $upIds = $this->findNodeIds([
            ['>=', $this->left, $neighbor[$this->left]],
            ['<=', $this->left, $neighbor[$this->right]],
        ]);
        $downIds = $this->findNodeIds([
            ['>=', $this->left, $this->model->{$this->left}],
            ['<=', $this->left, $this->model->{$this->right}]
        ]);
        if (sizeof($upIds) && sizeof($downIds)) {
            $up = $this->idToString($upIds);
            $down = $this->idToString($downIds);
            $up_differ = -abs($neighbor[$this->left] - $this->model->{$this->left});
            $down_differ = abs($this->model->{$this->right} - $neighbor[$this->right]);
            if ($this->counters($up_differ, [$up], [$up]) && $this->counters($down_differ, [$down], [$down])) {
                return true;
            } else {
                throw new Exception('移动失败');
            }
        } else {
            throw new Exception('数据错误');
        }
    }
    public function findNeighbor($condition, $order = 'DESC')
    {
        return $this->model->getDb()->createCommand(
            "select
                     {$this->left},
                     {$this->right},
                     {$this->grate}
                 from
                     {$this->model->tableName()}
                 where
                     {$this->buildWhere($condition)} " . "  ORDER BY {$this->left} {$order} limit 1 "
        )->queryOne();
    }
    public function findNodeIds(array $condition)
    {
        return $this->model->getDb()->createCommand(
            "select
                     {$this->model->primaryKey()[0]}
                 from
                     {$this->model->tableName()}
                 where
                     {$this->buildWhere($condition)} "
        )->queryAll();
    }
    public function idToString(array $ids)
    {
        $str = '(';
        $name = $this->model->primaryKey()[0];
        foreach ($ids as $id) {
            $str .= "'{$id[$name]}',";
        }
        $str = rtrim($str, ',');
        $str .= ')';
        return ['in', $name, str_replace(' ', '', $str)];
    }
    public function findParent($condition)
    {
        return $this->model->getDb()->createCommand(
            "select
                     {$this->left},
                     {$this->right},
                     {$this->grate}
                 from
                     {$this->model->tableName()}
                 where
                     {$this->buildWhere($condition)} " . " limit 1 "
        )->queryOne();
    }
    /**
     * 拼接where语句
     * @param $where
     * @return string
     */
    public function buildWhere($conditions = null)
    {
        return $this->where == null ? $this->setWhere($conditions) : $this->where . ' and ' . $this->setWhere($conditions);
    }
    /**
     * 生成where条件
     * @param $conditions
     */
    public function setWhere($conditions)
    {
        $where = '';
        if ($conditions != null) {
            foreach ($conditions as $condition) {
                if ($condition == null) {
                    return ('1=1');
                }
                if (strtolower($condition[0]) == 'in') {
                    $where .= "and {$condition[1]} {$condition[0]} {$condition[2]}";
                } else {
                    $where .= "and {$condition[1]} {$condition[0]} '{$condition[2]}' ";
                }
            }
        } else {
            return ('1=1');
        }
        return ltrim($where, 'and');
    }
    /**
     * @param array $condition
     * @return mixed 根据左右值的树结构,生成数组
     */
    public function getTreeArr(array $condition = array())
    {
        $TreeArr = array();
        //获取所有顶级节点
        $Toppk = $this->model->findBySql(
            "select
                     *
                 from
                     {$this->model->tableName()}
                 where {$this->buildWhere($condition)}
                 and " . $this->grate . "= 1 order by $this->left asc"
        )->asArray()->all();
        for ($i = 0; $i < count($Toppk); $i++) {
            $child = $this->getSon($Toppk[$i][$this->model->primaryKey()[0]]);
            $TreeArr[$Toppk[$i][$this->model->primaryKey()[0]]] = $this->ViewCate($Toppk[$i], $child);
        }
        return $TreeArr;
    }
    /**
     *递归回调函数，数组的组装。
     */
    private function ViewCate(array $parent, array $childs)
    {
        $childs_temp = $childs;
        $Treelist = $parent;
        for ($i = 0; $i < count($childs); $i++) {
            array_shift($childs_temp); //去掉数组头元素，即是获取在其左边的节点，再顺序执行
            if ($parent[$this->left] < $childs[$i][$this->left] &&
                $childs[$i][$this->left] < $parent[$this->right] &&
                (($parent[$this->grate] + 1) == $childs[$i][$this->grate])
            )//判断是否越级了，即末级节点结束，返回更高节点，不执行以下语句，返回上级，得到上级父节点，符合判断要求，继续执行！
            {
                if ($this->Ckchild($childs[$i])) {
                    //回调函数,返回子节点二维数组,生存多维数组.
                    $Treelist['children'][$childs[$i][$this->model->primaryKey()[0]]] = $this->ViewCate($childs[$i], $childs_temp);
                } else {
                    //为末节点时,生成此节点的二维数组.
                    $Treelist['children'][$childs[$i][$this->model->primaryKey()[0]]] = $childs[$i];
                }
            }
        }
        return $Treelist;
    }
    private function Ckchild(array $child)
    {
        if ($child[$this->right] - $child[$this->left] > 1) {
            return true;
        }
        return false;
    }
    /**
     *根据传入的pk值获取子节点树
     */
    public function getSon($parent_pk)
    {
        $pararr = $this->model->findOne($parent_pk);
        if ($pararr === null) {
            throw new Exception("请输入正确的父节点信息");
            exit;
        }
        $lft = $pararr->{$this->left};
        $rg = $pararr->{$this->right};
        $sonarr = $this->model->findBySql(
            "select * from " . $this->model->tableName() .
            " where $this->left>$lft and $this->right<$rg and $this->where order by $this->left asc"
        )->asArray()->all();
        return $sonarr;
    }
    /**
     *　是否有子节点
     */
    public function isHaveSon($condition)
    {
        $where = $this->amplyWhere($condition);
        $modelId = $this->model->primaryKey()[0];
        $pararr = $this->model->findOne($this->model->{$modelId});
        if ($pararr === null) {
            throw new Exception("请输入正确的父节点信息");
        }
        $lft = $pararr->{$this->left};
        $rg = $pararr->{$this->right};
        $sql =  "select * from " . $this->model->tableName() .
            " where {$where} and $this->left>$lft and $this->right<$rg and $this->where order by $this->left asc";
        $sonarr = $this->model->findBySql($sql)->one();
        return $sonarr;
    }
    /**
     * 是否为树结构
     * @return bool
     */
    public function isTree()
    {
        if(isset($this->model->{$this->left})) {
            return true;
        }
        return false;
    }
    /**
     * @param $condition
     * @return string
     */
    public function amplyWhere($condition)
    {
        $where = ' 1=1 ';
        foreach($condition as $key=>$val) {
            $where .= " and $key = '$val' ";
        }
        return $where;
    }

    /**
     *获取所有末级节点
     * @throws Exception
     */
    public function getEndNode($condition=[])
    {
        $EndNodes = array();
        $Toppk = $this->model->findBySql(
            "select
            *
            from
            {$this->model->tableName()}
            where {$this->buildWhere($condition)}
            order by $this->left asc"
        )->asArray()->all();

        for($i=0;$i<count($Toppk);$i++)
        {
            $child = $this->getSonNode($Toppk[$i]);
            if($child)
            {
                $EndNodes[] = $child;
            }
        }
        return $EndNodes;
    }

    /**
     *根据传入的父节点信息判断是否末级信息返回末级节点信息
     */
    public function getSonNode($parent)
    {
        $lft = $parent[$this->left];
        $rg = $parent[$this->right];

        $sonarr = $this->model->findBySql(
            "select * from ".$this->model->tableName().
            " where $this->left>$lft and $this->right<$rg"
        )->one();
        if($sonarr)
        {
            return false;
        }
        return $parent;
    }
    /**
     *通过条件，获取一组的节点树。
     */
    public function getViewCate(array $condition = array())
    {
        return $this->model->findBySql(
            "select
                     *
                 from
                     {$this->model->tableName()}
                 where
                     {$this->buildWhere($condition)}" . " order by $this->left asc"
        )->all();
    }
    /**
     *获取整个树，再进行顺序排列。
     */
    public function TreeAllCate()
    {
        return $this->model->findBySql(
            "select * from " . $this->model->tableName() .
            " where $this->where order by $this->left asc"
        )->all();
    }
    /**
     * 传过来的是要移动的模块
     * 平级移动节点。
     * @param Object $model
     * @throws Exception
     */
    public function HorMove($model)
    {
        //移动后的最新同级下一个节点
        $next = $this->model->findOne($this->model->{$this->model->next});
        //移动后的最新同级上一个节点
        $prev = $this->model->findOne($this->model->{$this->model->prev});
        //当前模块的父节点
        $parent_pk = $this->model->{$this->parent};
        if (!$parent_pk) {
            $parent_L = 0;
            $parent_R = $this->getMaxRight() + 1;
        } else {
            $parent = $this->model->findOne($this->model->{$this->parent});
            $parent_L = $parent->{$this->left};
            $parent_R = $parent->{$this->right};
        }
        if (!$prev) {
            $p_right = $parent_L;
        } else {
            $p_right = $prev->{$this->right};
        }
        if (!$next) {
            $n_left = $parent_R;
        } else {
            $n_left = $next->{$this->left};
        }
        //当前模块的左右值
        $m_left = $model->{$this->left};
        $m_right = $model->{$this->right};
        $num = $m_right - $m_left + 1;
        $len = $p_right < $m_left ? $m_left - $p_right - 1 : -($n_left - $m_right - 1);
        $transaction = Yii::$app->db->beginTransaction();
        try {
            //更新当前模块的左右值，使之变为负数，便于不影响其操作
            $sql = "update
            {$this->model->tableName()}
            set $this->left = -$this->left,$this->right = -$this->right
            where $this->left >= {$m_left} AND $this->right <= {$m_right}";
            Yii::$app->db->createCommand($sql)->execute();
            //更新节点移动前后经过的（中间）的节点信息
            if ($p_right < $m_left)//向上移
            {
                $sql = " update
                {$this->model->tableName()}
                set $this->left = $this->left+$num,$this->right = $this->right+$num
                where $this->right<$m_left and $this->left>$p_right";
                Yii::$app->db->createCommand($sql)->query();
            } else {
                $sql = " update
                {$this->model->tableName()}
                set $this->left = $this->left-$num,$this->right = $this->right-$num
                where $this->left>$m_right and $this->right<$n_left";
                Yii::$app->db->createCommand($sql)->query();
            }
            //更新自身信息
            $sql = " update
            {$this->model->tableName()}
            set $this->left = -$this->left-{$len},$this->right = -$this->right-{$len}
            where $this->left <= -{$m_left} AND $this->right >= -{$m_right}";
            Yii::$app->db->createCommand($sql)->execute();
            $transaction->commit();
        } catch (Exception $e) {
            $transaction->rollBack();
            throw new Exception($e->getMessage());
        }
    }
    /**
     * 获取树的最大值
     */
    public function getMaxRight()
    {
        $max = $this->model->find()->max($this->right);
        return $max;
    }
}